package geekstudy.week9;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 *
 * 239. 滑动窗口最大值
 * https://leetcode-cn.com/problems/sliding-window-maximum/
 *
 * 执行结果：  通过  显示详情
 *
 * 添加备注
 * 执行用时：76 ms, 在所有 Java 提交中击败了22.60% 的用户
 * 内存消耗：58.9 MB, 在所有 Java 提交中击败了13.91% 的用户
 *
 *
 */
public class Week9SlidingWindowMaximum {

    public int[] maxSlidingWindow(int[] nums, int k) {
        int length = nums.length;
        int result[] = new int[length - k + 1];
        PriorityQueue<int[]> priorityQueue = new PriorityQueue<int[]>(
                new Comparator<int[]>() {

                    @Override
                    public int compare(int[] c1, int[] c2) {
                        return c1[0] != c2[0] ? c2[0] - c1[0] : c2[1] - c1[1];
                    }

                }
        );

        for(int size = 0; size < k; size++) {
            priorityQueue.offer(new int[]{nums[size], size});
        }
        result[0] = priorityQueue.peek()[0];
        for(int size = k; size < length; size++) {
            priorityQueue.offer(new int[]{nums[size], size});
            for(; priorityQueue.peek()[1] <= size - k ;) {
                priorityQueue.poll();
            }
            result[size -k + 1] = priorityQueue.peek()[0];
        }

        return result;
    }
}
